home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 101_01 / ttt.c < prev    next >
Text File  |  1985-11-13  |  8KB  |  289 lines
  1.  
  2. /*
  3.     BD Software presents:
  4.  
  5.     Tic Tac Toe  (by exhaustive search)
  6.  
  7.     written by Leor Zolman
  8.            September 1979
  9.  
  10.     This program was written for use as the crux
  11.     of an article in BYTE (as yet to be published)
  12.     on BDS C, structured programming and gaming.
  13.  
  14.     It is also intended to get you addicted to C so
  15.     you'll go out and buy the 
  16.  
  17.         BD Software C Compiler
  18.  
  19.         only $110 on CP/M disk from:
  20.  
  21.         tiny c associates
  22.         post office box 269
  23.         holmdel, new jersey 07733
  24.  
  25.     The package includes the compiler, linking loader,
  26.     library manager, standard library of functions, many
  27.     interesting sample programs (such as "TELNET.C" for
  28.     using your computer as a terminal and allowing I/O
  29.     directly from modem to disk and vice-versa.) Also
  30.     included is a copy of the best reference book available
  31.     on the C language, written by the original implementors
  32.     at Bell Labs (the package may be purchased without
  33.     the book for $100.)
  34.  
  35. */
  36.  
  37.  
  38. #define X 1                /* The pieces on the board */
  39. #define O 5
  40. #define EMPTY 0
  41.  
  42. char board[9];                /* the playing board */
  43. char BEST;                /* move returned by "ttteval" */
  44. int wins[8][3];                /* table of  winning positions */
  45.  
  46.  
  47. main()
  48. {
  49.     int i;
  50.     int mefirst;            /* 1: computer goes first; 0: human */
  51.     int turn;            /* counts number of moves played */
  52.     int mypiece, hispiece;        /* who has x or o */
  53.     int mywins, hiswins, catwins;    /* game count */
  54.     int t;
  55.     srand(0);            /* initialize random generator */
  56.     initw(wins,"0,1,2,3,4,5,6,7,8,0,3,6,1,4,7,2,5,8,0,4,8,2,4,6");
  57.     mywins = hiswins = catwins = 0;
  58.     mefirst = 1;            /* let human go first */
  59.     printf("\n\nWelcome to BDS Tic Tac Toe!!\n");
  60.     printf("(In this version, X always goes first.\n");
  61.     printf("The board is arranged as follows:");
  62.     do {
  63.       mefirst = !mefirst;        /* reverse who goes first */
  64.       turn = 0;
  65.       display(1);
  66.       printf(mefirst ? "I go first...\n":
  67.                "You go first...\n");
  68.       clear();            /* clear the game board */
  69.            mypiece = mefirst ? X : O;     /* set who has got what */
  70.       hispiece  = mefirst ? O : X;
  71.       if (!mefirst) goto hismove;
  72.  
  73.  mymove: if (turn == 0)            /* Opening move may be random */
  74.         BEST = rand() % 9;
  75.       else if (turn == 1) {      /* Response to opener: */
  76.         if (board[4])
  77.             BEST = rand() % 2 * 6 +
  78.             rand() % 2 * 2;
  79.         else BEST = 4;
  80.        }
  81.       else {            /* OK, we're into the game... */
  82.         t = ttteval(mypiece,hispiece);
  83.         if (t == 1) printf("I've got ya!\n");
  84.         }
  85.        board[BEST] = mypiece;      /* make the move */
  86.        ++turn;
  87.        display(0);
  88.        if (win(mypiece)) {
  89.         ++mywins;
  90.         printf("\nI win!!!\n");
  91.         continue;
  92.         }
  93.        if (cats()) {
  94.         ++catwins;
  95.         printf("\nMeee-ow!\n");
  96.         continue;
  97.         }
  98.  
  99.   hismove: printf("Your move (1-9) ? ");
  100.        i = getchar() - 0x30;
  101.        if (i < 1 || i > 9 || board[i-1]) {
  102.         printf("\nIllegal!\n");
  103.         goto hismove;
  104.         }
  105.        board[i-1] = hispiece;
  106.        ++turn;
  107.        display(0);
  108.        if (win(hispiece)) {
  109.         ++hiswins;
  110.         printf("\nYou beat me!!\n");
  111.         continue;
  112.         }
  113.        if (cats()) {
  114.         ++catwins;
  115.         printf("\nOne for Morris.\n");
  116.         continue;
  117.         }
  118.        goto mymove;
  119.  
  120.     } while (ask("\nAnother game (y/n) ? "));
  121.  
  122.     printf("\n\nOK...Final score:\n");
  123.     printf("You won %d game",hiswins);
  124.     if (hiswins != 1) putchar('s');
  125.     printf(";\nI won %d game",mywins);
  126.     if (mywins != 1) putchar('s');
  127.     printf(";\nThe Cat got %d game",catwins);
  128.     if (catwins != 1) putchar('s');
  129.     printf(".\nSee ya later!!\n");
  130. }
  131.  
  132.  
  133. /*
  134.     The function "ttteval" returns an evaluation of
  135.     player x's position on the tic-tac-toe board. If he's
  136.     in a winning position, 1 is returned. If the best he
  137.     can hope for is a cat's game, 0 is returned. And, if
  138.     he's sure to lose if player y plays correctly, -1 is
  139.     returned. In any case, the best move available to 
  140.     player x is left in external variable BEST upon return
  141.     from ttteval.
  142.  
  143.     Note that a value of -1 is often returned while
  144.     recursive searching branches down into all possible
  145.     wins and losses, but with the program in the shape
  146.     it appears here, the outermost-level call to ttteval
  147.     (from the main program) will never produce a return
  148.     value of -1, since the computer has decided not to be
  149.     able to lose (the obviously logical choice of any
  150.     self-respecting problem-solver.)
  151.     In any case, the main program still bothers to 
  152.     consider the possibility of losing, so that if you
  153.     want to try inserting your own "ttteval" routine
  154.     in place of the one given, it dosn't have to be
  155.     perfect in order to work with the main program.
  156.     Tic-tac-toe is, of course, just about the only game
  157.     in which it is feasable to do an exhaustive search;
  158.     most game evaluation algorithms only go so deep and
  159.     then make a "static" evaluation, or estimate of the
  160.     player's status at the terminal position. That is how
  161.     all decent chess playing programs today work.
  162. */
  163.  
  164. ttteval(me,him)
  165. {
  166.     char i,safemove;
  167.     int v,loseflag;
  168.         /* first check for the 3 simple terminal
  169.            conditions:                */
  170.     if (win(me)) return 1;
  171.     if (win(him)) return -1;
  172.     if (cats()) return 0;
  173.         /* OK...now try all possible moves and see
  174.            our honorable opponent can do with each: */
  175.     loseflag = 1;
  176.     for (i=0; i<9; ++i) {
  177.         if (board[i]) continue; /* ignore non-moves! */
  178.         board[i] = me;        /* try the move...*/
  179.         v = ttteval(him,me);
  180.         board[i] = 0;        /* restore the empty space */
  181.         if (v == -1) {         /* if we force a loss, yey! */
  182.             BEST = i;
  183.             return 1;
  184.          }
  185.         if (v) continue;       /* uh oh! we shouldn't get beaten! */
  186.         loseflag = 0;        /* cat's game guaranteed at least */
  187.         safemove = i;
  188.      }
  189.     BEST = safemove;
  190.     return -loseflag;        /* if loseflag is true, this returns
  191.                        -1 to indicate a loss; else zero
  192.                        is returned (cat's game.)    */
  193. }
  194.  
  195. /*
  196.     This function returns true (non-zero) if player p
  197.     has three in a row on the board:
  198. */
  199.  
  200. win(p)
  201. {
  202.     char i;
  203.     for (i=0; i<8; ++i)
  204.         if (board[wins[i][0]] == p &&
  205.             board[wins[i][1]] == p &&
  206.             board[wins[i][2]] == p) return 1;
  207.     return 0;
  208. }
  209.  
  210.  
  211. /*
  212.     This function returns true if all nine squares are
  213.     taken (usually called after checking for a win, so
  214.     that all spaces filled indicates a cat's game)
  215. */
  216.  
  217. cats()
  218. {
  219.     char i;
  220.     for (i=0; i<9; ++i)
  221.         if (!board[i]) return 0;
  222.     return 1;
  223. }
  224.  
  225. /*
  226.     Function to clear the game board
  227. */
  228.  
  229. clear()
  230. {
  231.     char i;
  232.     for (i=0; i<9; ++i)
  233.         board[i] = EMPTY;
  234. }
  235.  
  236. /*
  237.     This one returns true if the player responds
  238.     positively to the prompt string, else returns false
  239.     (a good general-purpose yes/no asking function!)
  240. */
  241.  
  242. ask(s)
  243. char *s;
  244. {
  245.     char *gets(), c;
  246.     printf(s);
  247.     c = toupper(getchar());
  248.     return (c == 'Y');
  249. }
  250.  
  251. /*
  252.     Display the playing board with pieces if flag is 0,
  253.     or else with each square numbered from 1-9.
  254. */
  255.  
  256. display(flag)
  257. {
  258.     int i,j;
  259.     printf("\n\n");
  260.     for (i=0; i<9; i+=3) {
  261.         for (j=i; j< i+3; ++j) {
  262.             putchar(' ');
  263.             if (!flag)
  264.               switch(board[j]) {
  265.                 case EMPTY: putchar(' ');
  266.                     break;
  267.                 case X:    putchar('x');
  268.                     break;
  269.                 case O:    putchar('o');
  270.                }
  271.             else printf("%1d",j+1);
  272.             putchar(' ');
  273.             if (j != i+2) putchar('|');
  274.          }
  275.         putchar('\n');
  276.         if (i != 6) printf("---+---+---\n");
  277.      }
  278.     putchar('\n');
  279. }
  280. ][y] = p;
  281.     for (i= -1; i<=1; i++) for (j= -1; j<=1; j++) {
  282.         if ((i != 0 || j!=0)&&chkmv1(b,p,x,y,i,j)>0)
  283.             putmv1(b,p,x,y,ireturn row;
  284.           if (row == 'P') {
  285.             pboard(&master);
  286.             goto loop;
  287.            }
  288.           if (row == 0177 || row == '\n') goto err;
  289.